/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/count-and-say
   @Language: C++
   @Datetime: 20-01-15 14:23
   */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// Method 1, binary search, Time O((logn)^2)
class Solution {
public:
	int countNodes(TreeNode* root) {
		if (root==NULL) return 0;
		int left=0, right=0;
		for(TreeNode *l=root->left; l; ++left, l=l->left);
		for(TreeNode *r=root->right; r; ++right, r=r->left);
		if (left==right) return (1<<left)+countNodes(root->right);
		return (1<<right)+countNodes(root->left);
	}
};
